The present invention relates to the field of computer graphics and more specifically, efficient image rendering and polygon rasterization.
Image rendering is the process of transforming a collection of geometrically described objects into a pixel array which forms an image view of those objects. A particular view of a scene could be presented to a viewer by placing real objects in a space and allowing the viewer to view these objects from a viewpoint in that space through view opening. A two-dimensional simulated image of that scene can be generated for display on a display device to create the same view. To do this, the real objects are modelled by geometric expressions and coordinates in a space, a viewpoint and a view opening are positioned in the space, and the resulting image is rendered from this information. Typically, the view opening corresponds to a display surface of a display device. For a computer monitor, the display surface is the screen; for a printer, the display surface is a printed page.
Points in the virtual space are described by "world coordinates" and are usually represented by digital values in a digital image processing computer. Points on the display surface are described by "pixel grid" or "image" coordinates, and according to the well known art of ray tracing, points in the space defined in world coordinates can be mapped to points defined in pixel grid coordinates on the display surface, given the location of the viewpoint and the view opening in world coordinates.
Pixel grid coordinates are especially useful when rendering an image if the pixels of the display device are regularly spaced in a two-dimensional rectangular array and if the pixel grid coordinates are arranged such that either every pixel corner or every pixel center is located at integer pixel grid coordinates. Although it is arbitrary, herein pixel grid coordinates are such that the corner of each pixel is at integer coordinates. In real display devices, pixels might not be rectangles, but image manipulation is done nonetheless assuming that pixels have a finite area and are rectangular. Any deviation from this assumption can be addressed after the image is rendered in a number of ways which are beyond the present subject.
The input to an image rendering apparatus is a collection of geometrical descriptions of objects. The description might be as simple as the description of a uniformly red sphere, which is described by a center point, a radius, and a color. Other more complex objects could include descriptions of shape, size, orientation, surface features such as roughness, color, reflectivity (diffuse and/or specular), and self-luminosity. Although not strictly geometrical, a description of an object might include a collection of data describing a surface of the object, such as would be the case for the description of an object whose surface is an image of a digitized painting.
Where a display surface comprises a finite number of pixels, each of which can take on one of a finite number of colors, the final result of the rendering process is a block of data with one value for each of the finite number of pixels in the display device, the one value for a pixel indicating the color to be used for that pixel out of the finite number of colors in order to display the image. Such a display device is referred to herein as a "pixelated" or "raster" display device. "Raster" refers to the organization of pixels into rows, or scan lines, which typically run from left to right in an image, where an image is formed from multiple scan lines arranged from the top of the image to the bottom.
For brevity, "image" and "image block" herein refer to the block of data which is the expression of the image in the form usable by the display device. As should be apparent, a collection of object descriptions can exist without reference to a particular display device, but an image block is a function of the display device, or at least the number of pixels and the number of colors in the palette of colors available to a pixel. As should also be apparent, images can be processed and rendered without having a device to actually display the result.
Rendering a moderately complex set of objects into an image requires considerable computation. First, a number of calculations are needed to determine the location of the objects in the image and which objects obscure other objects. Then, the objects which are visible need to be projected onto the view opening to convert their descriptions from world coordinates to pixel grid coordinates. Visible objects also need to be shaded, and reflections and lighting must be taken into account.
Because of the processing needed, the image is often broken down into finite elements and each of these finite elements are separately processed, sometime in parallel. One way to break an image down is to divide the image into projections of surfaces in the object space. Because of the simplicity of triangles, typically, all polygons are further subdivided into triangles. The location of each of these triangles can be expressed by three points in pixel grid coordinates, but what is more useful is representing the triangle by the set of pixels which are within the triangle. This process is called polygon rasterization, since it is the process of converting the vectors of the polygon into a set of pixels in a pixel array's raster pattern. More precisely, the raster pattern for a polygon is the collection of pixels whose centers fall within the polygon. In some cases, the raster pattern includes pixels which are partially within the polygon, with some indication of the degree to which they are inside the polygon.
Because polygon rasterization necessarily results in a pixel pattern which is only an approximation of the polygon, it is important to accurately determine which pixels are part of the polygon and which pixels are not. Once pixels in the pixel array are associated with a particular polygon, functions which describe the color of the polygon over its visible surface are used to determine the colors of those associated pixels.
If a pixel is associated with the wrong polygon, it is likely to be colored incorrectly. For example, if the image shows two polygons which are supposed to describe a continuous surface of an object, each pixel along the boundary of the two polygons must be assigned to one or the other polygon. If the boundary is calculated incorrectly, one or more pixels might not be assigned to either polygon, in which case it would be colored the color of whatever is behind the two polygons. Then, if the background color is different from the color of the object represented by the two polygons, the image will show dots ("z poke-throughs") in the middle of the object, which are undesirable artifacts.
Therefore, it is important to correctly determine which pixels are inside a polygon. However, this determination must be done with a minimum of computation, since an image must be rendered quickly, and this determination is repeated many times for an image.
One method for polygon rasterization is shown by J. Pineda, "A Parallel Algorithm for Polygon Rasterization", Computer Graphics, Vol. 22, No. 4 (August 1988) (hereinafter "Pineda"). In Pineda, a triangle is rasterized by scanning the pixel array and evaluating three characteristic functions at each point. If the characteristic functions for a pixel all have the same sign, then the pixel is assigned to the inside of the triangle. However, rather than calculating the characteristic functions from scratch at each pixel, they are calculated by interpolation from prior function values and the derivative of the function values with respect to image coordinates. Although the functions are linear, and thus should have no error after repeated interpolation, when the process is performed in a digital computer with a finite precision, round-off errors will accumulate and could cause errors. Pineda addresses this problem by using high enough precision to give acceptable error (p. 19, second column). However, it is not disclosed how to determine what the error would be or what error is acceptable.
Pineda also discloses a method for scanning the triangle to be assured that each pixel in the triangle is found, and calculates the characteristic functions at each pixel found. However, this is not all that efficient, and often requires extra computation to locate triangle edges from scan line to scan line.
From the above it is seen that a faster and more accurate means for polygon rasterization is needed.